import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;


public class Parser {

	/**
	 * Given an NFA with two states and some number of transitions from start to accept, 
	 * return a copy of that NFA
	 * @param n the NFA to copy
	 * @return a copy of that NFA
	 */
	public static NFA copyPrimitiveNFA(NFA n) {
		State start = new State(false);
		State accept = new State(true);
		for(Character c : n.getStart().getTransitions().keySet()) {
			start.addTransition(c, accept);
		}
		return new NFA(start, accept);
	}

	/**
	 * Helper method to remove whitespace and surrounding parens from an expression.
	 * @param s the string to change
	 * @return the input string without whitespace or surrounding parens
	 */
	private static String stripParens(String s) {
		s = s.replaceAll("(?<!\\\\)\\s", "");
		int numOpen = 0;
		int i = 0;
		while(i < s.length()) {
			if(s.length() < 2 || s.charAt(0) != '(')
				break;
			if(s.charAt(i) == '(') numOpen++;
			else if(s.charAt(i) == ')') numOpen--;
			else if(s.charAt(i) == '\\') i++;
			i++;
			if(numOpen == 0 && i == s.length()) {
				s = s.substring(1, s.length()-1);
				i = 0;
			} else if(numOpen == 0)
				break;
		}

		return s;
	}

	/**
	 * Wrapper for our recursive descent parser
	 * @param str the string to parse, made up of IDs and +*()|
	 * @return the NFA for the regex
	 */
	public static NFA parse(String str, Map<String, NFA> map) {
		Scanner scan = new Scanner(str);
		LinkedList<NFA> list = new LinkedList<NFA>();
		String line;
		NFA temp;
		while(scan.hasNextLine()) {
			line = scan.nextLine();
			String[] arr = line.split("\\s", 2);
			temp = parseOne(arr[1], map);
			temp.getAccept().setToken(arr[0]);
			list.add(temp);
		}
		NFA[] ret = new NFA[list.size()];
		int i = 0;
		for(NFA n : list)
			ret[i++] = n;

		return NFA.unionNoEpsilon(ret);
	}

	/**
	 * Wrapper for one line of our recursive descent parser
	 * @param str the string to parse
	 * @param map a map of character classes to their NFAs
	 * @return the generated NFA
	 */
	public static NFA parseOne(String str, Map<String, NFA> map) {
		return tryUnion(stripParens(str), map);
	}

	/**
	 * Look for unions in our string.  If they exist, split them and parse. If not, look for concatenations.
	 * @param str the string to parse
	 * @param map a map of character classes to their NFAs
	 * @return the generated NFA
	 */
	public static NFA tryUnion(String str, Map<String, NFA> map) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		int unmatched = 0, i = 0;
		boolean escape = false;
		for(char c : str.toCharArray()) {
			if(escape)
				escape = false;
			else
				if(c == '\\')
					escape = true;
				else if(c == '(')
					unmatched++;
				else if(c==')')
					unmatched--;
				else if(c=='|' && unmatched == 0) {
					list.addLast(i);
				}
			i++;
		}

		if(list.isEmpty()) //We don't have anything to union at the top level, try for concats.
			return tryConcat(str, map);

		NFA[] nfas = new NFA[list.size()+1];
		int start = 0, end = -1;
		i = 0;
		for(Integer temp : list) {
			start = end+1;
			end = temp;
			if(start != end)
				nfas[i++] = parseOne(str.substring(start, end), map);
			else
				nfas[i++] = NFA.epsilonNFA();
		}
		if(end < str.length()-1)
			nfas[i] = parseOne(str.substring(end+1), map);
		else
			nfas[i] = NFA.epsilonNFA();


		return NFA.union(nfas);
	}

	/**
	 * Look for concatenations in our string.  If they exist, split them and parse. If not, look for stars or pluses.
	 * @param str the string to parse
	 * @param map a map of character classes to their NFAs
	 * @return the generated NFA
	 */
	public static NFA tryConcat(String str, Map<String, NFA> map) {
		//We have either literals (a, \+), character classes ([a-zA-Z]), IDs ($IDENT), or parens ()
		int openParens = 0;
		int i = 0;
		LinkedList<NFA> nfas = new LinkedList<NFA>();
		int start;
		while(i < str.length()) {
			if(str.charAt(i) == '$') {  //IDs
				start = i;
				i++;
				while(i < str.length() && Character.isLetterOrDigit(str.charAt(i))) { //Find the name of the ID
					i++;
				}
				nfas.add(copyPrimitiveNFA(map.get(str.substring(start, i)))); //Add the ID to the list of NFAs
			} else if(str.charAt(i) == '(') { //Parens block
				start = i;
				openParens++;
				i++;
				while(openParens > 0 && i < str.length()) {
					if(str.charAt(i) == '\\') i++;
					else if(str.charAt(i) == '(') openParens++;
					else if(str.charAt(i) == ')') openParens--;
					i++;
				}

				if(i < str.length() && (str.charAt(i) == '*' || str.charAt(i) == '+')) {
					i++;
					nfas.add(tryStarPlus(str.substring(start, i), map));
				} else {
					nfas.add(parseOne(str.substring(start, i), map));
				}

			} else if(str.charAt(i) == '[') {  //Char class
				openParens++;
				start = i;
				i++;
				while(openParens > 0 && i < str.length()) {
					if(str.charAt(i) == '\\') i++;
					else if(str.charAt(i) == '[') openParens++;
					else if(str.charAt(i) == ']') openParens--;
					i++;
				}
				openParens = 0;
				if(str.charAt(start+1) == '^') {
					String s = str.substring(start, i);
					while(i < str.length() && str.charAt(i) != '$' && str.charAt(i) != '[')  i++;
					start = i;
					if(str.charAt(start) == '$') {
						i++;
						while(i < str.length() && Character.isLetterOrDigit(str.charAt(i))) { //Find the name of the ID
							i++;
						}
						nfas.add(ScannerGenerator.charClassToNFA(ScannerGenerator.subClassCharClass(s, map.get(str.substring(start, i)).getStart().getTransitions().keySet())));
					} else if(str.charAt(start) == '[') {
						openParens = 1;
						while(openParens > 0 && i < str.length()) {
							if(str.charAt(i) == '\\') i++;
							else if(str.charAt(i) == '[') openParens++;
							else if(str.charAt(i) == ']') openParens--;
							i++;
						}
						openParens = 0;
						nfas.add(ScannerGenerator.charClassToNFA(ScannerGenerator.subClassCharClass(s, ScannerGenerator.charClassToSet(str.substring(start, i)))));
					}
				} else {
				
					if(i < str.length() && (str.charAt(i) == '*' || str.charAt(i) == '+')) {
						i++;
						nfas.add(ScannerGenerator.charClassToNFA(ScannerGenerator.charClassToSet(str.substring(start, i))));
					} else {
						nfas.add(ScannerGenerator.charClassToNFA(ScannerGenerator.charClassToSet(str.substring(start, i))));
					}
				}
			} else if(str.charAt(i) == '\\') { //Escape character
				i++;
				if(i+1 < str.length() && str.charAt(i+1) == '*')
					nfas.add(NFA.star(literalTransitionNFA(str.charAt(i++))));
				else if(i+1 < str.length() && str.charAt(i+1) == '+')
					nfas.add(NFA.concatenate(literalTransitionNFA(str.charAt(i)), NFA.star(literalTransitionNFA(str.charAt(i++)))));
				else
					nfas.add(literalTransitionNFA(str.charAt(i)));
				i++;
			} else if(Character.isWhitespace(str.charAt(i))) {
				i++;
			} else {
				if(i+1 < str.length() && str.charAt(i+1) == '*')
					nfas.add(NFA.star(literalTransitionWithDotNFA(str.charAt(i++))));
				else if(i+1 < str.length() && str.charAt(i+1) == '+')
					nfas.add(NFA.concatenate(literalTransitionWithDotNFA(str.charAt(i)), NFA.star(literalTransitionWithDotNFA(str.charAt(i++)))));
				else
					nfas.add(literalTransitionWithDotNFA(str.charAt(i)));
				i++;
			}	
		}
		NFA n = nfas.remove(0);
		for(NFA nfa : nfas) {
			n = NFA.concatenate(n, nfa);
		}
		return n;
	}


	/**
	 * Look for stars or pluses in our string.  If they exist, split them and parse. If not, look for concatenations.
	 * @param str the string to parse
	 * @param map a map of character classes to their NFAs
	 * @return the generated NFA
	 */
	public static NFA tryStarPlus(String str, Map<String, NFA> map) {
		int i;
		int openParens = 0;
		for(i = 0; i < str.length(); i++) {
			if(str.charAt(i) == '(') openParens++;
			else if(str.charAt(i) == ')') openParens--;
			else if(str.charAt(i) == '\\') i++;
			else if(openParens == 0 &&(str.charAt(i) == '*' || str.charAt(i) == '+')) break;
		}

		if(i == str.length()) { //No star or plus, just do the concat.
			return parseOne(str.substring(1, str.length()-1), map);
		} else if(str.charAt(i) == '+') { //Found a plus, so do cat(NFA, NFA*)
			NFA n = parseOne(str.substring(0, i), map);
			NFA n2 = parseOne(str.substring(0, i), map);
			return NFA.concatenate(n, NFA.star(n2));
		} else if(str.charAt(i) == '*') { //found a star, NFA*
			return NFA.star(parseOne(str.substring(0, i), map));
		}
		return null;
	}



	/**
	 * Convenience method for generating an NFA with one transition on c from start to accept
	 * @param c the character to transition on
	 * @return an NFA with a transition on c from start to accept
	 */
	private static NFA literalTransitionNFA(char c) {
		State start = new State(false);
		State accept = new State(true);
		start.addTransition(c, accept);
		return new NFA(start, accept);
	}
	
	/**
	 * Convenience method for generating an NFA with one transition on c from start to accept
	 * @param c the character to transition on
	 * @return an NFA with a transition on c from start to accept
	 */
	private static NFA literalTransitionWithDotNFA(char c) {
		
		State start = new State(false);
		State accept = new State(true);
		if(c == '.') {  //Deal with . character classes
			for(char i = 0; i < 128; i++) {
				if(i != State.EPSILON)
					start.addTransition(i, accept);
			}
		} else
			start.addTransition(c, accept);
		return new NFA(start, accept);
	}

}
